package sortsuanfa;
import java.util.Arrays;

/**
 * 归并排序
 * <p>
 * 切分数组，使得左右两边的小数组先有序，然后在进行左右两边合并
 *
 * @author Hongten
 * @created 19 Mar, 2019
 */
public class Merge {

    public static void main(String[] args) {
        int[] a = {5, 4, 3, 2, 1};
        mergesort(a, 0, a.length - 1);
        /**
         * output:
         * [2, 4, 5, 6, 7, 8, 9, 10]
         */
        System.out.println(Arrays.toString(a));
    }

    public static void mergesort(int[] array, int left, int right) {
        if (left != right) {
            int mid = (left + right) >> 1;
            mergesort(array, left, mid);
            mergesort(array, mid + 1, right);
            merge(array, left, mid + 1, right);
        }
    }

    private static void merge(int[] array, int left, int mid, int right) {
        int leftSize = mid - left;
        int rightSize = right - mid + 1;
        int[] leftArray = new int[leftSize];
        int[] rightArray = new int[rightSize];
        for (int i = left; i < mid; i++) {
            leftArray[i - left] = array[i];
        }
        for (int i = mid; i <= right; i++) {
            rightArray[i - mid] = array[i];
        }
        int i = 0, j = 0;
        while (i < leftSize && j < rightSize) {
            if (leftArray[i] < rightArray[j]) {
                array[left++] = leftArray[i++];
            } else {
                array[left++] = rightArray[j++];
            }
        }
        while (i < leftSize) {
            array[left++] = leftArray[i++];
        }
        while (j < rightSize) {
            array[left++] = rightArray[j++];
        }
    }
}

//    public static void mergeSort(int[] array, int left, int right) {
//        if (left != right) {
//            int mid = (left + right) >> 1;
//            mergeSort(array, left, mid);
//            mergeSort(array, mid + 1, right);
//            merge(array, left, mid + 1, right);
//        }
//    }
//
//    public static void merge(int[] array, int l, int mid, int r) {
//        int leftSize = mid - l;
//        int rightSize = r - mid + 1;
//        int[] leftArray = new int[leftSize];
//        int[] rightArray = new int[rightSize];
//        for (int i = l; i < mid; i++) {
//            leftArray[i - l] = array[i];
//        }
//
//        for (int i = mid; i <= r; i++) {
//            rightArray[i - mid] = array[i];
//        }
//        int i = 0, j = 0;
//        int k = l;
//        while (i < leftSize && j < rightSize) {
//            if (leftArray[i] < rightArray[j]) {
//                array[k++] = leftArray[i++];
//            } else {
//                array[k++] = rightArray[j++];
//            }
//        }
//
//        while (i < leftSize) {
//            array[k++] = leftArray[i++];
//        }
//        while (j < rightSize) {
//            array[k++] = leftArray[j++];
//        }
//    }
//}